package gsolver;

import org.apache.commons.math.genetics.AbstractListChromosome;
import org.apache.commons.math.genetics.InvalidRepresentationException;
import org.apache.commons.math.optimization.linear.SimplexSolver;
import org.apache.commons.math.optimization.linear.LinearObjectiveFunction;
import org.apache.commons.math.optimization.linear.LinearConstraint;
import org.apache.commons.math.optimization.linear.Relationship;
import org.apache.commons.math.optimization.GoalType;
import org.apache.commons.math.optimization.RealPointValuePair;
import org.apache.commons.math.optimization.OptimizationException;
import org.apache.commons.math.linear.RealVector;
import org.apache.commons.math.linear.OpenMapRealVector;

import java.util.List;
import java.util.Set;
import java.util.Collection;
import java.util.Collections;
import java.util.ArrayList;
import java.util.Comparator;

import gproblem.GSupplyLinkProblem;
import gproblem.GJobData;

import gsolution.GJobVariable;
import gsolution.GSupplyLinkSolution;

/**
 * Chromosome pour notre algorithme génétique.
 * On utilise le codage suivant:
 * Un gène est un lot, et l'ordre des gènes est l'ordre de livraison des lots.
 *
 * Formellement, c'est une partition ordonnée de {1, ..., n}.
 *
 * Ici, ce codage est représenté par une liste de lots, où un lot est un ensemble d'entier,
 * chacun représentant un job.
 */
public class GChromosome extends AbstractListChromosome<gsolver.Lot> {
    static private GSupplyLinkProblem problem = null;

    private double fitnessValue;

    private RealPointValuePair fitnessSimplex;

    /**
     * Constructeur. Ne fait pas de copie de ses arguments.
     */
    public GChromosome(List<Lot> representation) {
	super(representation);
	fitnessSimplex = null;
	fitnessValue = calculeFitness();
    }

    /**
     * Constructeur. Ne fait pas de copie de ses arguments.
     */
    public GChromosome(Lot[] representation) {
	super(representation);
	fitnessSimplex = null;
	fitnessValue = calculeFitness();
    }

    static public void setProblem(GSupplyLinkProblem newProblem) {
	problem = newProblem;
    }

    static public GSupplyLinkProblem getProblem() {
	return problem;
    }

    /**
     * Vérifie qu'une représentation est valide. Si elle est invalide, lance une
     * exception.
     */
    public void checkValidity(List<Lot> chromosomeRepresentation) 
	throws InvalidRepresentationException {
	for (int i = 0; i < chromosomeRepresentation.size(); i++) {
	    for (int j = i + 1; j < chromosomeRepresentation.size(); j++) {
		Set<Integer> intersection = chromosomeRepresentation.get(i).getCopyJobs();

		intersection.retainAll(chromosomeRepresentation.get(j).getJobs());

		if (!intersection.isEmpty()) {
		    throw new InvalidRepresentationException("Representation invalide: pas une partition: " + representationToString(chromosomeRepresentation));
		}
	    }
	}
	
	int i = 0;
	for (Lot lot : chromosomeRepresentation) {
	    for (Integer job : lot.getJobs()) {
		i++;
	    }
	}
	if (i < problem.getN()) {
	    throw new InvalidRepresentationException("Representation invalide: pas une partition: " + representationToString(chromosomeRepresentation));
	}
    }

    /**
     * Construit un nouveau chromosome à partir de la représentation en argument.
     */
    public GChromosome newFixedLengthChromosome(List<Lot> chromosomeRepresentation) {
	return new GChromosome(chromosomeRepresentation);
    }

    /**
     * Calcule la fitness de la solution.
     */
    public double fitness() {
	return fitnessValue;
    }

    public double calculeFitness() {
	return fitnessSimplex(problem.getJobData(), 
			      problem.getTransporters().get(0).getCapacity()).getValue();
    }

    /**
     * Calcule la fitness en appliquant l'algorithme du simplex au programme
     * linéaire simplifié. L'algorithme génétique fixe la constitution des lots,
     * on peut donc raisonner sur les dates de livraison des lots plutôt que sur
     * celle des jobs individuels. 
     *
     * A chaque lot on associe une date maximale de livraison correspondant au minimum
     * des dates de livraison des jobs du lot, un coût de stockage minimum correspondant
     * au coût de stockage si le lot est livré à la date maximale, et un coût de stockage
     * unitaire du lot qui correspond à la somme des coûts de stockage unitaire de chaque
     * job du lot.
     *
     * Avec les lots constitués, on a donc plus qu'une fonction objectif à minimiser:
     *
     * Σ coutUnitaireLot * dateLivraisonLot
     *
     * les autres termes étant constant, on les ajoutera après pour obtenir le coût total.
     * Chaque lot étant constitué de façon correcte, on a plus à se soucier des contraintes
     * liées à la capacité du conteneur, ni aux contraintes liées à l'égalité des dates de
     * départ des jobs d'un même lot car on manipule les dates de livraison des lots.
     *
     * L'algorithme du simplexe a une complexité temporelle polynomiale en general, mais ici
     * notre programme linéaire à une forme particulière, ce qui devrait rendre la résolution
     * plus rapide - de façon non formelle, il suffit de maximiser les dates de livraison,
     * sauf lorsque les dates de livraison maximales sont trop proches, c'est à dire lorsque
     *
     * dateLivraisonMaxLot(i + 1) - dateLivraisonMaxLot(i) <= tempsDeLivraison
     *
     * TODO: meilleure analyse de complexité
     */
    public RealPointValuePair fitnessSimplex(GJobData[] jobData, double capaciteTransporteur) {
	if (fitnessSimplex == null) {
	    SimplexSolver solver = new SimplexSolver();

	    LinearObjectiveFunction objectif = construireObjectif(jobData);
	    Collection<LinearConstraint> contraintes = construireContraintes(jobData,
									     capaciteTransporteur);
	    try {
		fitnessSimplex = solver.optimize(objectif, contraintes, GoalType.MINIMIZE, true);
	    } catch (OptimizationException e) {
		System.err.println("Erreur de calcul de la fitness par simplex.");
		return null;
	    }
	}

	return fitnessSimplex;
    }

    private LinearObjectiveFunction construireObjectif(GJobData[] jobData) {
	double[] coutUnitaireLot = new double[getLength()];
	double coutsTransports = getLength() * problem.getTransporter(0).getDeliveryCost();
	double sommeCoutMinimumLots = 0;

	for (int i = 0; i < getLength(); i++) {
	    coutUnitaireLot[i] = getRepresentation().get(i).coutStockageUnitaire();
	    sommeCoutMinimumLots += getRepresentation().get(i).coutMinimal();
	}
	
	return new LinearObjectiveFunction(coutUnitaireLot, sommeCoutMinimumLots);
    }

    private Collection<LinearConstraint> construireContraintes(GJobData[] jobData, 
							       double capaciteTransporteur) {
	/* On a une contrainte de borne supérieure par lot
	   et une contrainte de temps de livraison pour chaque lot sauf le dernier. 
	   C'est pourquoi on a 2 * nombreDeLots - 1 contraintes. */
	ArrayList<LinearConstraint> contraintes = 
	    new ArrayList<LinearConstraint>(2 * getLength() - 1);
	/* Ici on utilise une représentation creuse du vecteur car celui-ci contient
	   au plus 2 éléments non nuls, ce qui permet entre autre une copie en temps
	   constant. */
	
	/* construit les contraintes de date maximale de livraison */
	for (int i = 0; i < getLength(); i++) {
	    RealVector contrainte = new OpenMapRealVector(getLength());
	    contrainte.setEntry(i, 1);
	    contraintes.add(i, new LinearConstraint(contrainte, Relationship.LEQ, 
						    getRepresentation().get(i).dateLivraisonMax()));
	}

	/* construit les contraintes de temps de livraison */
	for (int i = 0; i < getLength() - 1; i++) {
	    RealVector contrainte = new OpenMapRealVector(getLength());
	    contrainte.setEntry(i, -1);
	    contrainte.setEntry(i + 1, 1);
	    contraintes.add(i + getLength(), 
			    new LinearConstraint(contrainte, Relationship.LEQ,
						 capaciteTransporteur));
	}
	
	return contraintes;
    }

    /**
     * Retourne une approximation de la fitness du chromosome. L'algorithme est le suivant:
     * Pour chaque dans l'ordre de livraison, et pour chaque lot dans l'ordre inverse de
     * livraison, on essaie de le fixer à sa date de livraison max. Si ce n'est pas possible
     * à cause d'un conflit de temps de livraison avec un lot déjà fixé, on décale du temps
     * nécessaire.
     */
    private double fitnessApproximee() {
	double tempsDeTransport = problem.getTransporter(0).getDeliveryTime();
	double[] dates = new double[getRepresentation().size()];

	dates[getRepresentation().size() - 1] = 
	    getRepresentation().get(getRepresentation().size() - 1).dateLivraisonMax();
	for (int i = getRepresentation().size() - 2; i >= 0; i--) {
	    dates[i] = getRepresentation().get(i).dateLivraisonMax();
	    if (Math.abs(dates[i] - dates[i+1]) <= tempsDeTransport) {
		dates[i] = dates[i+1] - tempsDeTransport + 10E-5;
	    }
	}

	return calculerCout(dates);
    }

    private double calculerCout(double[] dates) {
	double coutsTransports = getLength() * problem.getTransporter(0).getDeliveryCost();
	double cout = 0;

	for (int i = 0; i < getLength(); i++) {
	    cout += getRepresentation().get(i).coutMinimal() +
		getRepresentation().get(i).coutStockageUnitaire() * 
		(getRepresentation().get(i).dateLivraisonMax() - dates[i]);
	}

	return cout + coutsTransports;
    }

    public List<Lot> getRepresentation() {
	return super.getRepresentation();
    }

    public GSupplyLinkSolution toGSupplyLinkSolutionSimplex() {
	RealPointValuePair solution = 
	    fitnessSimplex(problem.getJobData(), 
			   problem.getTransporters().get(0).getCapacity());
	GJobVariable[] processingSchedule = new GJobVariable[problem.getN()];

	int i = 0;

	for (int j = 0; j < getLength(); j++) {
	    for (Integer job : getRepresentation().get(j).getJobs()) {
		processingSchedule[job] = new GJobVariable(j, solution.getPoint()[j]);
		i++;
	    }
	}

	return new GSupplyLinkSolution(problem, processingSchedule, getLength(), 0, 0,
				       0, false);
    }

    public static String representationToString(List<Lot> representation) {
	String resultat = "";

	for (Lot lot : representation) {
	    resultat += lot;
	}

	return resultat;
    }
    
    public String toString() {
	return representationToString(getRepresentation());
    }
}